/***********************************************************************
*
* Copyright (c) 2012-2025 Barbara Geller
* Copyright (c) 2012-2025 Ansel Sermersheim
*
* Copyright (c) 2015 The Qt Company Ltd.
* Copyright (c) 2012-2016 Digia Plc and/or its subsidiary(-ies).
* Copyright (c) 2008-2012 Nokia Corporation and/or its subsidiary(-ies).
*
* This file is part of CopperSpice.
*
* CopperSpice is free software. You can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public License
* version 2.1 as published by the Free Software Foundation.
*
* CopperSpice is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
*
* https://www.gnu.org/licenses/
*
***********************************************************************/

#include <qgraphics_anchorlayout_p.h>

#include <qalgorithms.h>
#include <qapplication.h>
#include <qfile.h>
#include <qlinkedlist.h>
#include <qstack.h>
#include <qwidget.h>

#ifndef QT_NO_GRAPHICSVIEW

// To ensure all variables inside the simplex solver are non-negative, we limit the size of anchors
// in the interval [-limit, limit]. Then before sending them to the simplex solver we add "limit" as
// an offset, so that they are actually calculated in the interval [0, 2 * limit]
// To avoid numerical errors in platforms where we use single precision, a tighter limit for the
// variables range is used

const qreal g_offset = (sizeof(qreal) == sizeof(double)) ? QWIDGETSIZE_MAX : QWIDGETSIZE_MAX / 32;

QGraphicsAnchorPrivate::QGraphicsAnchorPrivate()
   : layoutPrivate(nullptr), data(nullptr), sizePolicy(QSizePolicy::Fixed), preferredSize(0), hasSize(true)
{
}

QGraphicsAnchorPrivate::~QGraphicsAnchorPrivate()
{
   if (data) {
      // QGraphicsAnchor was already deleted, must clean up this pointer to avoid a double deletion
      data->graphicsAnchor = nullptr;

      layoutPrivate->removeAnchor(data->from, data->to);
   }
}

void QGraphicsAnchorPrivate::setSizePolicy(QSizePolicy::Policy policy)
{
   if (sizePolicy != policy) {
      sizePolicy = policy;
      layoutPrivate->q_func()->invalidate();
   }
}

void QGraphicsAnchorPrivate::setSpacing(qreal value)
{
   if (!data) {
      qWarning("QGraphicsAnchor::setSpacing() Anchor does not exist");
      return;
   }

   if (hasSize && (preferredSize == value)) {
      return;
   }

   // anchor has an user-defined size
   hasSize = true;
   preferredSize = value;

   layoutPrivate->q_func()->invalidate();
}

void QGraphicsAnchorPrivate::unsetSpacing()
{
   if (!data) {
      qWarning("QGraphicsAnchor::setSpacing() Anchor does not exist");
      return;
   }

   // Return to standard direction
   hasSize = false;

   layoutPrivate->q_func()->invalidate();
}

qreal QGraphicsAnchorPrivate::spacing() const
{
   if (!data) {
      qWarning("QGraphicsAnchor::setSpacing() Anchor does not exist");
      return 0;
   }

   return preferredSize;
}


static void applySizePolicy(QSizePolicy::Policy policy, qreal minSizeHint, qreal prefSizeHint, qreal maxSizeHint,
      qreal *minSize, qreal *prefSize, qreal *maxSize)
{
   // minSize, prefSize and maxSize are initialized
   // with item's preferred Size: this is QSizePolicy::Fixed.
   //
   // Then we check each flag to find the resultant QSizePolicy,
   // according to the following table:
   //
   //      constant               value
   // QSizePolicy::Fixed            0
   // QSizePolicy::Minimum       GrowFlag
   // QSizePolicy::Maximum       ShrinkFlag
   // QSizePolicy::Preferred     GrowFlag | ShrinkFlag
   // QSizePolicy::Ignored       GrowFlag | ShrinkFlag | IgnoreFlag

   if (cs_enum_cast(policy) & cs_enum_cast(QSizePolicy::ShrinkFlag)) {
      *minSize = minSizeHint;
   } else {
      *minSize = prefSizeHint;
   }

   if (cs_enum_cast(policy) & cs_enum_cast(QSizePolicy::GrowFlag)) {
      *maxSize = maxSizeHint;
   } else {
      *maxSize = prefSizeHint;
   }

   // Note that these two initializations are affected by the previous flags
   if (cs_enum_cast(policy) & cs_enum_cast(QSizePolicy::IgnoreFlag)) {
      *prefSize = *minSize;
   } else {
      *prefSize = prefSizeHint;
   }
}

AnchorData::~AnchorData()
{
   if (graphicsAnchor) {
      // Remove reference to ourself to avoid double removal in
      // QGraphicsAnchorPrivate dtor.
      graphicsAnchor->d_func()->data = nullptr;

      delete graphicsAnchor;
   }
}

void AnchorData::refreshSizeHints(const QLayoutStyleInfo *styleInfo)
{
   QSizePolicy::Policy policy;
   qreal minSizeHint;
   qreal prefSizeHint;
   qreal maxSizeHint;

   if (item) {
      // this is a CS anchor, fetch size information from the item
      if (isLayoutAnchor) {
         minSize  = 0;
         prefSize = 0;
         maxSize  = QWIDGETSIZE_MAX;

         if (isCenterAnchor) {
            maxSize /= 2;
         }

         minPrefSize = prefSize;
         maxPrefSize = maxSize;
         return;

      } else {
         if (orientation == QGraphicsAnchorLayoutPrivate::Horizontal) {
            policy = item->sizePolicy().horizontalPolicy();
            minSizeHint = item->effectiveSizeHint(Qt::MinimumSize).width();
            prefSizeHint = item->effectiveSizeHint(Qt::PreferredSize).width();
            maxSizeHint = item->effectiveSizeHint(Qt::MaximumSize).width();
         } else {
            policy = item->sizePolicy().verticalPolicy();
            minSizeHint = item->effectiveSizeHint(Qt::MinimumSize).height();
            prefSizeHint = item->effectiveSizeHint(Qt::PreferredSize).height();
            maxSizeHint = item->effectiveSizeHint(Qt::MaximumSize).height();
         }

         if (isCenterAnchor) {
            minSizeHint /= 2;
            prefSizeHint /= 2;
            maxSizeHint /= 2;
         }
      }

   } else {
      // It is a user-created anchor, fetch size information from the associated QGraphicsAnchor
      Q_ASSERT(graphicsAnchor);
      QGraphicsAnchorPrivate *anchorPrivate = graphicsAnchor->d_func();

      // Policy, min and max sizes are straightforward
      policy = anchorPrivate->sizePolicy;
      minSizeHint = 0;
      maxSizeHint = QWIDGETSIZE_MAX;

      // Preferred Size
      if (anchorPrivate->hasSize) {
         // Anchor has user-defined size
         prefSizeHint = anchorPrivate->preferredSize;
      } else {
         // Fetch size information from style
         const Qt::Orientation orient = Qt::Orientation(QGraphicsAnchorLayoutPrivate::edgeOrientation(from->m_edge) + 1);
         qreal s = styleInfo->defaultSpacing(orient);
         if (s < 0) {
            QSizePolicy::ControlType controlTypeFrom = from->m_item->sizePolicy().controlType();
            QSizePolicy::ControlType controlTypeTo = to->m_item->sizePolicy().controlType();
            s = styleInfo->perItemSpacing(controlTypeFrom, controlTypeTo, orient);

            // ### Currently we do not support negative anchors inside the graph.
            // To avoid those being created by a negative style spacing, we must
            // make this test.
            if (s < 0) {
               s = 0;
            }
         }
         prefSizeHint = s;
      }
   }

   // Fill minSize, prefSize and maxSize based on policy and sizeHints
   applySizePolicy(policy, minSizeHint, prefSizeHint, maxSizeHint,
      &minSize, &prefSize, &maxSize);

   minPrefSize = prefSize;
   maxPrefSize = maxSize;

   // Set the anchor effective sizes to preferred.
   //
   // Note: The idea here is that all items should remain at their
   // preferred size unless where that's impossible.  In cases where
   // the item is subject to restrictions (anchored to the layout
   // edges, for instance), the simplex solver will be run to
   // recalculate and override the values we set here.
   sizeAtMinimum = prefSize;
   sizeAtPreferred = prefSize;
   sizeAtMaximum = prefSize;
}

void ParallelAnchorData::updateChildrenSizes()
{
   firstEdge->sizeAtMinimum = sizeAtMinimum;
   firstEdge->sizeAtPreferred = sizeAtPreferred;
   firstEdge->sizeAtMaximum = sizeAtMaximum;

   if (secondForward()) {
      secondEdge->sizeAtMinimum = sizeAtMinimum;
      secondEdge->sizeAtPreferred = sizeAtPreferred;
      secondEdge->sizeAtMaximum = sizeAtMaximum;
   } else {
      secondEdge->sizeAtMinimum = -sizeAtMinimum;
      secondEdge->sizeAtPreferred = -sizeAtPreferred;
      secondEdge->sizeAtMaximum = -sizeAtMaximum;
   }

   firstEdge->updateChildrenSizes();
   secondEdge->updateChildrenSizes();
}

bool ParallelAnchorData::calculateSizeHints()
{
   // Normalize second child sizes.
   // A negative anchor of sizes min, minPref, pref, maxPref and max, is equivalent
   // to a forward anchor of sizes -max, -maxPref, -pref, -minPref, -min
   qreal secondMin;
   qreal secondMinPref;
   qreal secondPref;
   qreal secondMaxPref;
   qreal secondMax;

   if (secondForward()) {
      secondMin = secondEdge->minSize;
      secondMinPref = secondEdge->minPrefSize;
      secondPref = secondEdge->prefSize;
      secondMaxPref = secondEdge->maxPrefSize;
      secondMax = secondEdge->maxSize;
   } else {
      secondMin = -secondEdge->maxSize;
      secondMinPref = -secondEdge->maxPrefSize;
      secondPref = -secondEdge->prefSize;
      secondMaxPref = -secondEdge->minPrefSize;
      secondMax = -secondEdge->minSize;
   }

   minSize = qMax(firstEdge->minSize, secondMin);
   maxSize = qMin(firstEdge->maxSize, secondMax);

   // This condition means that the maximum size of one anchor being simplified is smaller than
   // the minimum size of the other anchor. The consequence is that there won't be a valid size
   // for this parallel setup.
   if (minSize > maxSize) {
      return false;
   }

   // Preferred size calculation
   // The calculation of preferred size is done as follows:
   //
   // 1) Check whether one of the child anchors is the layout structural anchor
   //    If so, we can simply copy the preferred information from the other child,
   //    after bounding it to our minimum and maximum sizes.
   //    If not, then we proceed with the actual calculations.
   //
   // 2) The whole algorithm for preferred size calculation is based on the fact
   //    that, if a given anchor cannot remain at its preferred size, it'd rather
   //    grow than shrink.
   //
   //    What happens though is that while this affirmative is true for simple
   //    anchors, it may not be true for sequential anchors that have one or more
   //    reversed anchors inside it. That happens because when a sequential anchor
   //    grows, any reversed anchors inside it may be required to shrink, something
   //    we try to avoid, as said above.
   //
   //    To overcome this, besides their actual preferred size "prefSize", each anchor
   //    exports what we call "minPrefSize" and "maxPrefSize". These two values define
   //    a surrounding interval where, if required to move, the anchor would rather
   //    remain inside.
   //
   //    For standard anchors, this area simply represents the region between
   //    prefSize and maxSize, which makes sense since our first affirmation.
   //    For composed anchors, these values are calculated as to reduce the global
   //    "damage", that is, to reduce the total deviation and the total amount of
   //    anchors that had to shrink.

   if (firstEdge->isLayoutAnchor) {
      prefSize = qBound(minSize, secondPref, maxSize);
      minPrefSize = qBound(minSize, secondMinPref, maxSize);
      maxPrefSize = qBound(minSize, secondMaxPref, maxSize);
   } else if (secondEdge->isLayoutAnchor) {
      prefSize = qBound(minSize, firstEdge->prefSize, maxSize);
      minPrefSize = qBound(minSize, firstEdge->minPrefSize, maxSize);
      maxPrefSize = qBound(minSize, firstEdge->maxPrefSize, maxSize);
   } else {
      // Calculate the intersection between the "preferred" regions of each child
      const qreal lowerBoundary =
         qBound(minSize, qMax(firstEdge->minPrefSize, secondMinPref), maxSize);
      const qreal upperBoundary =
         qBound(minSize, qMin(firstEdge->maxPrefSize, secondMaxPref), maxSize);
      const qreal prefMean =
         qBound(minSize, (firstEdge->prefSize + secondPref) / 2, maxSize);

      if (lowerBoundary < upperBoundary) {
         // If there is an intersection between the two regions, this intersection
         // will be used as the preferred region of the parallel anchor itself.
         // The preferred size will be the bounded average between the two preferred
         // sizes.
         prefSize = qBound(lowerBoundary, prefMean, upperBoundary);
         minPrefSize = lowerBoundary;
         maxPrefSize = upperBoundary;
      } else {
         // If there is no intersection, we have to attribute "damage" to at least
         // one of the children. The minimum total damage is achieved in points
         // inside the region that extends from (1) the upper boundary of the lower
         // region to (2) the lower boundary of the upper region.
         // Then, we expose this region as _our_ preferred region and once again,
         // use the bounded average as our preferred size.
         prefSize = qBound(upperBoundary, prefMean, lowerBoundary);
         minPrefSize = upperBoundary;
         maxPrefSize = lowerBoundary;
      }
   }

   // See comment in AnchorData::refreshSizeHints() about sizeAt* values
   sizeAtMinimum = prefSize;
   sizeAtPreferred = prefSize;
   sizeAtMaximum = prefSize;

   return true;
}

static QPair<QGraphicsAnchorLayoutPrivate::Interval, qreal> getFactor(qreal value, qreal min,
      qreal minPref, qreal pref, qreal maxPref, qreal max)
{
   QGraphicsAnchorLayoutPrivate::Interval interval;
   qreal lower;
   qreal upper;

   if (value < minPref) {
      interval = QGraphicsAnchorLayoutPrivate::MinimumToMinPreferred;
      lower = min;
      upper = minPref;
   } else if (value < pref) {
      interval = QGraphicsAnchorLayoutPrivate::MinPreferredToPreferred;
      lower = minPref;
      upper = pref;
   } else if (value < maxPref) {
      interval = QGraphicsAnchorLayoutPrivate::PreferredToMaxPreferred;
      lower = pref;
      upper = maxPref;
   } else {
      interval = QGraphicsAnchorLayoutPrivate::MaxPreferredToMaximum;
      lower = maxPref;
      upper = max;
   }

   qreal progress;
   if (upper == lower) {
      progress = 0;
   } else {
      progress = (value - lower) / (upper - lower);
   }

   return qMakePair(interval, progress);
}

static qreal interpolate(const QPair<QGraphicsAnchorLayoutPrivate::Interval, qreal> &factor,
   qreal min, qreal minPref, qreal pref, qreal maxPref, qreal max)
{
   qreal lower = 0;
   qreal upper = 0;

   switch (factor.first) {
      case QGraphicsAnchorLayoutPrivate::MinimumToMinPreferred:
         lower = min;
         upper = minPref;
         break;
      case QGraphicsAnchorLayoutPrivate::MinPreferredToPreferred:
         lower = minPref;
         upper = pref;
         break;
      case QGraphicsAnchorLayoutPrivate::PreferredToMaxPreferred:
         lower = pref;
         upper = maxPref;
         break;
      case QGraphicsAnchorLayoutPrivate::MaxPreferredToMaximum:
         lower = maxPref;
         upper = max;
         break;
   }

   return lower + factor.second * (upper - lower);
}

void SequentialAnchorData::updateChildrenSizes()
{
   // Band here refers if the value is in the Minimum To Preferred
   // band (the lower band) or the Preferred To Maximum (the upper band).

   const QPair<QGraphicsAnchorLayoutPrivate::Interval, qreal> minFactor =
      getFactor(sizeAtMinimum, minSize, minPrefSize, prefSize, maxPrefSize, maxSize);
   const QPair<QGraphicsAnchorLayoutPrivate::Interval, qreal> prefFactor =
      getFactor(sizeAtPreferred, minSize, minPrefSize, prefSize, maxPrefSize, maxSize);
   const QPair<QGraphicsAnchorLayoutPrivate::Interval, qreal> maxFactor =
      getFactor(sizeAtMaximum, minSize, minPrefSize, prefSize, maxPrefSize, maxSize);

   // XXX This is not safe if Vertex simplification takes place after the sequential
   // anchor is created. In that case, "prev" will be a group-vertex, different from
   // "from" or "to", that _contains_ one of them.
   AnchorVertex *prev = from;

   for (int i = 0; i < m_edges.count(); ++i) {
      AnchorData *e = m_edges.at(i);

      const bool edgeIsForward = (e->from == prev);
      if (edgeIsForward) {
         e->sizeAtMinimum = interpolate(minFactor, e->minSize, e->minPrefSize,
               e->prefSize, e->maxPrefSize, e->maxSize);
         e->sizeAtPreferred = interpolate(prefFactor, e->minSize, e->minPrefSize,
               e->prefSize, e->maxPrefSize, e->maxSize);
         e->sizeAtMaximum = interpolate(maxFactor, e->minSize, e->minPrefSize,
               e->prefSize, e->maxPrefSize, e->maxSize);
         prev = e->to;
      } else {
         Q_ASSERT(prev == e->to);
         e->sizeAtMinimum = interpolate(minFactor, e->maxSize, e->maxPrefSize,
               e->prefSize, e->minPrefSize, e->minSize);
         e->sizeAtPreferred = interpolate(prefFactor, e->maxSize, e->maxPrefSize,
               e->prefSize, e->minPrefSize, e->minSize);
         e->sizeAtMaximum = interpolate(maxFactor, e->maxSize, e->maxPrefSize,
               e->prefSize, e->minPrefSize, e->minSize);
         prev = e->from;
      }

      e->updateChildrenSizes();
   }
}

void SequentialAnchorData::calculateSizeHints()
{
   minSize = 0;
   prefSize = 0;
   maxSize = 0;
   minPrefSize = 0;
   maxPrefSize = 0;

   AnchorVertex *prev = from;

   for (int i = 0; i < m_edges.count(); ++i) {
      AnchorData *edge = m_edges.at(i);

      const bool edgeIsForward = (edge->from == prev);
      if (edgeIsForward) {
         minSize += edge->minSize;
         prefSize += edge->prefSize;
         maxSize += edge->maxSize;
         minPrefSize += edge->minPrefSize;
         maxPrefSize += edge->maxPrefSize;
         prev = edge->to;
      } else {
         Q_ASSERT(prev == edge->to);
         minSize -= edge->maxSize;
         prefSize -= edge->prefSize;
         maxSize -= edge->minSize;
         minPrefSize -= edge->maxPrefSize;
         maxPrefSize -= edge->minPrefSize;
         prev = edge->from;
      }
   }

   // See comment in AnchorData::refreshSizeHints() about sizeAt* values
   sizeAtMinimum = prefSize;
   sizeAtPreferred = prefSize;
   sizeAtMaximum = prefSize;
}

#if defined(CS_SHOW_DEBUG_GUI_GRAPHICSVIEW)
void AnchorData::dump(int indent)
{
   if (type == Parallel) {
      qDebug("%*s type: parallel:", indent, "");
      ParallelAnchorData *p = static_cast<ParallelAnchorData *>(this);
      p->firstEdge->dump(indent + 2);
      p->secondEdge->dump(indent + 2);
   } else if (type == Sequential) {
      SequentialAnchorData *s = static_cast<SequentialAnchorData *>(this);
      int kids = s->m_edges.count();
      qDebug("%*s type: sequential(%d):", indent, "", kids);
      for (int i = 0; i < kids; ++i) {
         s->m_edges.at(i)->dump(indent + 2);
      }
   } else {
      qDebug("%*s type: Normal:", indent, "");
   }
}

#endif

QSimplexConstraint *GraphPath::constraint(const GraphPath &path) const
{
   // Calculate
   QSet<AnchorData *> cPositives;
   QSet<AnchorData *> cNegatives;
   QSet<AnchorData *> intersection;

   cPositives = positives + path.negatives;
   cNegatives = negatives + path.positives;

   intersection = cPositives & cNegatives;

   cPositives -= intersection;
   cNegatives -= intersection;

   // Fill
   QSimplexConstraint *c = new QSimplexConstraint;
   QSet<AnchorData *>::iterator i;
   for (i = cPositives.begin(); i != cPositives.end(); ++i) {
      c->variables.insert(*i, 1.0);
   }

   for (i = cNegatives.begin(); i != cNegatives.end(); ++i) {
      c->variables.insert(*i, -1.0);
   }

   return c;
}

#if defined(CS_SHOW_DEBUG_GUI_GRAPHICSVIEW)
QString GraphPath::toString() const
{
   QString string(QLatin1String("Path: "));

   for (AnchorData *edge : positives) {
      string += QString::fromLatin1(" (+++) %1").formatArg(edge->toString());
   }

   for (AnchorData *edge : negatives) {
      string += QString::fromLatin1(" (---) %1").formatArg(edge->toString());
   }

   return string;
}
#endif

QGraphicsAnchorLayoutPrivate::QGraphicsAnchorLayoutPrivate()
   : calculateGraphCacheDirty(true), styleInfoDirty(true)
{
   for (int i = 0; i < NOrientations; ++i) {
      for (int j = 0; j < 3; ++j) {
         sizeHints[i][j] = -1;
      }
      interpolationProgress[i] = -1;

      spacings[i] = -1;
      graphHasConflicts[i]   = false;

      layoutFirstVertex[i]   = nullptr;
      layoutCentralVertex[i] = nullptr;
      layoutLastVertex[i]    = nullptr;
   }
}

Qt::AnchorPoint QGraphicsAnchorLayoutPrivate::oppositeEdge(Qt::AnchorPoint edge)
{
   switch (edge) {
      case Qt::AnchorLeft:
         edge = Qt::AnchorRight;
         break;
      case Qt::AnchorRight:
         edge = Qt::AnchorLeft;
         break;
      case Qt::AnchorTop:
         edge = Qt::AnchorBottom;
         break;
      case Qt::AnchorBottom:
         edge = Qt::AnchorTop;
         break;
      default:
         break;
   }
   return edge;
}


AnchorData *QGraphicsAnchorLayoutPrivate::addAnchorMaybeParallel(AnchorData *newAnchor, bool *feasible)
{
   Orientation orientation = Orientation(newAnchor->orientation);
   Graph<AnchorVertex, AnchorData> &g = graph[orientation];
   *feasible = true;

   // If already exists one anchor where newAnchor is supposed to be, we create a parallel
   // anchor.
   if (AnchorData *oldAnchor = g.takeEdge(newAnchor->from, newAnchor->to)) {
      ParallelAnchorData *parallel = new ParallelAnchorData(oldAnchor, newAnchor);

      // The parallel anchor will "replace" its children anchors in
      // every center constraint that they appear.

      // ### If the dependent (center) anchors had reference(s) to their constraints, we
      // could avoid traversing all the itemCenterConstraints.
      QList<QSimplexConstraint *> &constraints = itemCenterConstraints[orientation];

      AnchorData *children[2] = { oldAnchor, newAnchor };
      QList<QSimplexConstraint *> *childrenConstraints[2] = { &parallel->m_firstConstraints,
            &parallel->m_secondConstraints
         };

      for (int i = 0; i < 2; ++i) {
         AnchorData *child = children[i];
         QList<QSimplexConstraint *> *childConstraints = childrenConstraints[i];

         // We need to fix the second child constraints if the parallel group will have the
         // opposite direction of the second child anchor. For the point of view of external
         // entities, this anchor was reversed. So if at some point we say that the parallel
         // has a value of 20, this mean that the second child (when reversed) will be
         // assigned -20.
         const bool needsReverse = i == 1 && !parallel->secondForward();

         if (!child->isCenterAnchor) {
            continue;
         }

         parallel->isCenterAnchor = true;

         for (int j = 0; j < constraints.count(); ++j) {
            QSimplexConstraint *c = constraints[j];
            if (c->variables.contains(child)) {
               childConstraints->append(c);
               qreal v = c->variables.take(child);
               if (needsReverse) {
                  v *= -1;
               }
               c->variables.insert(parallel, v);
            }
         }
      }

      // At this point we can identify that the parallel anchor is not feasible, e.g. one
      // anchor minimum size is bigger than the other anchor maximum size.
      *feasible = parallel->calculateSizeHints();
      newAnchor = parallel;
   }

   g.createEdge(newAnchor->from, newAnchor->to, newAnchor);
   return newAnchor;
}

// does not add the created anchor to the graph. This should be done by the caller
static AnchorData *createSequence(Graph<AnchorVertex, AnchorData> *graph,
      AnchorVertex *before, const QVector<AnchorVertex *> &vertices, AnchorVertex *after)
{
   AnchorVertex *prev = before;
   QVector<AnchorData *> edges;

   const int numVertices = vertices.count();
   edges.reserve(numVertices + 1);

   // Take from the graph, the edges that will be simplificated
   for (int i = 0; i < numVertices; ++i) {
      AnchorVertex *next = vertices.at(i);
      AnchorData *ad = graph->takeEdge(prev, next);
      Q_ASSERT(ad);
      edges.append(ad);
      prev = next;
   }

   // Take the last edge (not covered in the loop above)
   AnchorData *ad = graph->takeEdge(vertices.last(), after);
   Q_ASSERT(ad);
   edges.append(ad);

   // Create sequence
   SequentialAnchorData *sequence = new SequentialAnchorData(vertices, edges);
   sequence->from = before;
   sequence->to = after;

   sequence->calculateSizeHints();

   return sequence;
}

bool QGraphicsAnchorLayoutPrivate::simplifyGraph(Orientation orientation)
{
   if (items.isEmpty()) {
      return true;
   }

   // Vertex simplification
   if (!simplifyVertices(orientation)) {
      restoreVertices(orientation);
      return false;
   }

   // Anchor simplification
   bool dirty;
   bool feasible = true;
   do {
      dirty = simplifyGraphIteration(orientation, &feasible);
   } while (dirty && feasible);

   // Note that if we are not feasible, we fallback and make sure that the graph is fully restored
   if (!feasible) {
      restoreSimplifiedGraph(orientation);
      restoreVertices(orientation);
      return false;
   }

   return true;
}

static AnchorVertex *replaceVertex_helper(AnchorData *data, AnchorVertex *oldV, AnchorVertex *newV)
{
   AnchorVertex *other;
   if (data->from == oldV) {
      data->from = newV;
      other = data->to;
   } else {
      data->to = newV;
      other = data->from;
   }
   return other;
}

bool QGraphicsAnchorLayoutPrivate::replaceVertex(Orientation orientation, AnchorVertex *oldV,
   AnchorVertex *newV, const QList<AnchorData *> &edges)
{
   Graph<AnchorVertex, AnchorData> &g = graph[orientation];
   bool feasible = true;

   for (int i = 0; i < edges.count(); ++i) {
      AnchorData *ad = edges[i];
      AnchorVertex *otherV = replaceVertex_helper(ad, oldV, newV);

#if defined(CS_SHOW_DEBUG_GUI_GRAPHICSVIEW)
      ad->name = QString::fromLatin1("%1 --to--> %2").formatArg(ad->from->toString()).formatArg(ad->to->toString());
#endif

      bool newFeasible;
      AnchorData *newAnchor = addAnchorMaybeParallel(ad, &newFeasible);
      feasible &= newFeasible;

      if (newAnchor != ad) {
         // A parallel was created, we mark that in the list of anchors created by vertex
         // simplification. This is needed because we want to restore them in a separate step
         // from the restoration of anchor simplification.
         anchorsFromSimplifiedVertices[orientation].append(newAnchor);
      }

      g.takeEdge(oldV, otherV);
   }

   return feasible;
}

bool QGraphicsAnchorLayoutPrivate::simplifyVertices(Orientation orientation)
{
   Q_Q(QGraphicsAnchorLayout);
   Graph<AnchorVertex, AnchorData> &g = graph[orientation];

   // We'll walk through vertices
   QStack<AnchorVertex *> stack;
   stack.push(layoutFirstVertex[orientation]);
   QSet<AnchorVertex *> visited;

   while (!stack.isEmpty()) {
      AnchorVertex *v = stack.pop();
      visited.insert(v);

      // Each adjacent of 'v' is a possible vertex to be merged. So we traverse all of
      // them. Since once a merge is made, we might add new adjacents, and we don't want to
      // pass two times through one adjacent. The 'index' is used to track our position.
      QList<AnchorVertex *> adjacents = g.adjacentVertices(v);
      int index = 0;

      while (index < adjacents.count()) {
         AnchorVertex *next = adjacents.at(index);
         index++;

         AnchorData *data = g.edgeData(v, next);
         const bool bothLayoutVertices = v->m_item == q && next->m_item == q;
         const bool zeroSized = !data->minSize && !data->maxSize;

         if (!bothLayoutVertices && zeroSized) {

            // Create a new vertex pair, note that we keep a list of those vertices so we can
            // easily process them when restoring the graph.
            AnchorVertexPair *newV = new AnchorVertexPair(v, next, data);
            simplifiedVertices[orientation].append(newV);

            // Collect the anchors of both vertices, the new vertex pair will take their place
            // in those anchors
            const QList<AnchorVertex *> &vAdjacents = g.adjacentVertices(v);
            const QList<AnchorVertex *> &nextAdjacents = g.adjacentVertices(next);

            for (int i = 0; i < vAdjacents.count(); ++i) {
               AnchorVertex *adjacent = vAdjacents.at(i);
               if (adjacent != next) {
                  AnchorData *ad = g.edgeData(v, adjacent);
                  newV->m_firstAnchors.append(ad);
               }
            }

            for (int i = 0; i < nextAdjacents.count(); ++i) {
               AnchorVertex *adjacent = nextAdjacents.at(i);
               if (adjacent != v) {
                  AnchorData *ad = g.edgeData(next, adjacent);
                  newV->m_secondAnchors.append(ad);

                  // We'll also add new vertices to the adjacent list of the new 'v', to be
                  // created as a vertex pair and replace the current one.
                  if (!adjacents.contains(adjacent)) {
                     adjacents.append(adjacent);
                  }
               }
            }

            // ### merge this loop into the ones that calculated m_firstAnchors/m_secondAnchors?
            // Make newV take the place of v and next
            bool feasible = replaceVertex(orientation, v, newV, newV->m_firstAnchors);
            feasible &= replaceVertex(orientation, next, newV, newV->m_secondAnchors);

            // Update the layout vertex information if one of the vertices is a layout vertex.
            AnchorVertex *layoutVertex = nullptr;
            if (v->m_item == q) {
               layoutVertex = v;
            } else if (next->m_item == q) {
               layoutVertex = next;
            }

            if (layoutVertex) {
               // Layout vertices always have m_item == q...
               newV->m_item = q;
               changeLayoutVertex(orientation, layoutVertex, newV);
            }

            g.takeEdge(v, next);

            // If a non-feasibility is found, we leave early and cancel the simplification
            if (!feasible) {
               return false;
            }

            v = newV;
            visited.insert(newV);

         } else if (!visited.contains(next) && !stack.contains(next)) {
            // If the adjacent is not fit for merge and it wasn't visited by the outermost
            // loop, we add it to the stack.
            stack.push(next);
         }
      }
   }

   return true;
}

bool QGraphicsAnchorLayoutPrivate::simplifyGraphIteration(QGraphicsAnchorLayoutPrivate::Orientation orientation,
   bool *feasible)
{
   Q_Q(QGraphicsAnchorLayout);
   Graph<AnchorVertex, AnchorData> &g = graph[orientation];

   QSet<AnchorVertex *> visited;
   QStack<QPair<AnchorVertex *, AnchorVertex *>> stack;
   stack.push(qMakePair(static_cast<AnchorVertex *>(nullptr), layoutFirstVertex[orientation]));
   QVector<AnchorVertex *> candidates;

   // Walk depth-first, in the stack we store start of the candidate sequence (beforeSequence)
   // and the vertex to be visited.
   while (!stack.isEmpty()) {
      QPair<AnchorVertex *, AnchorVertex *> pair = stack.pop();
      AnchorVertex *beforeSequence = pair.first;
      AnchorVertex *v = pair.second;

      // The basic idea is to determine whether we found an end of sequence,
      // if that's the case, we stop adding vertices to the candidate list
      // and do a simplification step.
      //
      // A vertex can trigger an end of sequence if
      // (a) it is a layout vertex, we don't simplify away the layout vertices;
      // (b) it does not have exactly 2 adjacents;
      // (c) its next adjacent is already visited (a cycle in the graph).
      // (d) the next anchor is a center anchor.

      const QList<AnchorVertex *> &adjacents = g.adjacentVertices(v);
      const bool isLayoutVertex = v->m_item == q;
      AnchorVertex *afterSequence = v;
      bool endOfSequence = false;

      //
      // Identify the end cases.
      //

      // Identifies cases (a) and (b)
      endOfSequence = isLayoutVertex || adjacents.count() != 2;

      if (!endOfSequence) {
         // This is a tricky part. We peek at the next vertex to find out whether
         //
         // - we already visited the next vertex (c);
         // - the next anchor is a center (d).
         //
         // Those are needed to identify the remaining end of sequence cases. Note that unlike
         // (a) and (b), we preempt the end of sequence by looking into the next vertex.

         // Peek at the next vertex
         AnchorVertex *after;
         if (candidates.isEmpty()) {
            after = (beforeSequence == adjacents.last() ? adjacents.first() : adjacents.last());
         } else {
            after = (candidates.last() == adjacents.last() ? adjacents.first() : adjacents.last());
         }

         // ### At this point we assumed that candidates will not contain 'after', this may not hold
         // when simplifying FLOATing anchors.
         Q_ASSERT(!candidates.contains(after));

         const AnchorData *data = g.edgeData(v, after);
         Q_ASSERT(data);
         const bool cycleFound = visited.contains(after);

         // Now cases (c) and (d)...
         endOfSequence = cycleFound || data->isCenterAnchor;

         if (!endOfSequence) {
            // If it's not an end of sequence, then the vertex didn't trigger neither of the
            // previously three cases, so it can be added to the candidates list.
            candidates.append(v);
         } else if (cycleFound && (beforeSequence != after)) {
            afterSequence = after;
            candidates.append(v);
         }
      }

      //
      // Add next non-visited vertices to the stack.
      //
      for (int i = 0; i < adjacents.count(); ++i) {
         AnchorVertex *next = adjacents.at(i);
         if (visited.contains(next)) {
            continue;
         }

         // If current vertex is an end of sequence, and it'll reset the candidates list. So
         // the next vertices will build candidates lists with the current vertex as 'before'
         // vertex. If it's not an end of sequence, we keep the original 'before' vertex,
         // since we are keeping the candidates list.
         if (endOfSequence) {
            stack.push(qMakePair(v, next));
         } else {
            stack.push(qMakePair(beforeSequence, next));
         }
      }

      visited.insert(v);

      if (!endOfSequence || candidates.isEmpty()) {
         continue;
      }

      //
      // Create a sequence for (beforeSequence, candidates, afterSequence).
      //

      // One restriction we have is to not simplify half of an anchor and let the other half
      // unsimplified. So we remove center edges before and after the sequence.
      const AnchorData *firstAnchor = g.edgeData(beforeSequence, candidates.first());
      if (firstAnchor->isCenterAnchor) {
         beforeSequence = candidates.first();
         candidates.remove(0);

         // If there's not candidates to be simplified, leave.
         if (candidates.isEmpty()) {
            continue;
         }
      }

      const AnchorData *lastAnchor = g.edgeData(candidates.last(), afterSequence);
      if (lastAnchor->isCenterAnchor) {
         afterSequence = candidates.last();
         candidates.remove(candidates.count() - 1);

         if (candidates.isEmpty()) {
            continue;
         }
      }

      //
      // Add the sequence to the graph.
      //

      AnchorData *sequence = createSequence(&g, beforeSequence, candidates, afterSequence);

      // If 'beforeSequence' and 'afterSequence' already had an anchor between them, we'll
      // create a parallel anchor between the new sequence and the old anchor.
      bool newFeasible;
      AnchorData *newAnchor = addAnchorMaybeParallel(sequence, &newFeasible);

      if (!newFeasible) {
         *feasible = false;
         return false;
      }

      // When a new parallel anchor is create in the graph, we finish the iteration and return
      // true to indicate a new iteration is needed. This happens because a parallel anchor
      // changes the number of adjacents one vertex has, possibly opening up oportunities for
      // building candidate lists (when adjacents == 2).
      if (newAnchor != sequence) {
         return true;
      }

      // If there was no parallel simplification, we'll keep walking the graph. So we clear the
      // candidates list to start again.
      candidates.clear();
   }

   return false;
}

void QGraphicsAnchorLayoutPrivate::restoreSimplifiedAnchor(AnchorData *edge)
{
   Graph<AnchorVertex, AnchorData> &g = graph[edge->orientation];

   if (edge->type == AnchorData::Normal) {
      g.createEdge(edge->from, edge->to, edge);

   } else if (edge->type == AnchorData::Sequential) {
      SequentialAnchorData *sequence = static_cast<SequentialAnchorData *>(edge);

      for (int i = 0; i < sequence->m_edges.count(); ++i) {
         AnchorData *data = sequence->m_edges.at(i);
         restoreSimplifiedAnchor(data);
      }

      delete sequence;

   } else if (edge->type == AnchorData::Parallel) {

      // Skip parallel anchors that were created by vertex simplification, they will be processed
      // later, when restoring vertex simplification.
      // ### we could improve this check bit having a bit inside 'edge'
      if (anchorsFromSimplifiedVertices[edge->orientation].contains(edge)) {
         return;
      }

      ParallelAnchorData *parallel = static_cast<ParallelAnchorData *>(edge);
      restoreSimplifiedConstraints(parallel);

      // ### Because of the way parallel anchors are created in the anchor simplification
      // algorithm, we know that one of these will be a sequence, so it'll be safe if the other
      // anchor create an edge between the same vertices as the parallel.
      Q_ASSERT(parallel->firstEdge->type == AnchorData::Sequential
         || parallel->secondEdge->type == AnchorData::Sequential);
      restoreSimplifiedAnchor(parallel->firstEdge);
      restoreSimplifiedAnchor(parallel->secondEdge);

      delete parallel;
   }
}

void QGraphicsAnchorLayoutPrivate::restoreSimplifiedConstraints(ParallelAnchorData *parallel)
{
   if (!parallel->isCenterAnchor) {
      return;
   }

   for (int i = 0; i < parallel->m_firstConstraints.count(); ++i) {
      QSimplexConstraint *c = parallel->m_firstConstraints.at(i);
      qreal v = c->variables[parallel];
      c->variables.remove(parallel);
      c->variables.insert(parallel->firstEdge, v);
   }

   // When restoring, we might have to revert constraints back. See comments on
   // addAnchorMaybeParallel().
   const bool needsReverse = !parallel->secondForward();

   for (int i = 0; i < parallel->m_secondConstraints.count(); ++i) {
      QSimplexConstraint *c = parallel->m_secondConstraints.at(i);
      qreal v = c->variables[parallel];
      if (needsReverse) {
         v *= -1;
      }
      c->variables.remove(parallel);
      c->variables.insert(parallel->secondEdge, v);
   }
}

void QGraphicsAnchorLayoutPrivate::restoreSimplifiedGraph(Orientation orientation)
{
   // Restore anchor simplification
   Graph<AnchorVertex, AnchorData> &g = graph[orientation];
   QList<QPair<AnchorVertex *, AnchorVertex *>> connections = g.connections();
   for (int i = 0; i < connections.count(); ++i) {
      AnchorVertex *v1 = connections.at(i).first;
      AnchorVertex *v2 = connections.at(i).second;
      AnchorData *edge = g.edgeData(v1, v2);

      // We restore only sequential anchors and parallels that were not created by
      // vertex simplification.
      if (edge->type == AnchorData::Sequential
         || (edge->type == AnchorData::Parallel &&
            !anchorsFromSimplifiedVertices[orientation].contains(edge))) {

         g.takeEdge(v1, v2);
         restoreSimplifiedAnchor(edge);
      }
   }

   restoreVertices(orientation);
}

void QGraphicsAnchorLayoutPrivate::restoreVertices(Orientation orientation)
{
   Q_Q(QGraphicsAnchorLayout);

   Graph<AnchorVertex, AnchorData> &g = graph[orientation];
   QList<AnchorVertexPair *> &toRestore = simplifiedVertices[orientation];

   // Since we keep a list of parallel anchors and vertices that were created during vertex
   // simplification, we can now iterate on those lists instead of traversing the graph
   // recursively.

   // First, restore the constraints changed when we created parallel anchors. Note that this
   // works at this point because the constraints doesn't depend on vertex information and at
   // this point it's always safe to identify whether the second child is forward or backwards.
   // In the next step, we'll change the anchors vertices so that would not be possible anymore.
   QList<AnchorData *> &parallelAnchors = anchorsFromSimplifiedVertices[orientation];

   for (int i = parallelAnchors.count() - 1; i >= 0; --i) {
      ParallelAnchorData *parallel = static_cast<ParallelAnchorData *>(parallelAnchors.at(i));
      restoreSimplifiedConstraints(parallel);
   }

   // Then, we will restore the vertices in the inverse order of creation, this way we ensure that
   // the vertex being restored was not wrapped by another simplification.
   for (int i = toRestore.count() - 1; i >= 0; --i) {
      AnchorVertexPair *pair = toRestore.at(i);
      QList<AnchorVertex *> adjacents = g.adjacentVertices(pair);

      // Restore the removed edge, this will also restore both vertices 'first' and 'second' to
      // the graph structure.
      AnchorVertex *first = pair->m_first;
      AnchorVertex *second = pair->m_second;
      g.createEdge(first, second, pair->m_removedAnchor);

      // Restore the anchors for the first child vertex
      for (int j = 0; j < pair->m_firstAnchors.count(); ++j) {
         AnchorData *ad = pair->m_firstAnchors.at(j);
         Q_ASSERT(ad->from == pair || ad->to == pair);

         replaceVertex_helper(ad, pair, first);
         g.createEdge(ad->from, ad->to, ad);
      }

      // Restore the anchors for the second child vertex
      for (int j = 0; j < pair->m_secondAnchors.count(); ++j) {
         AnchorData *ad = pair->m_secondAnchors.at(j);
         Q_ASSERT(ad->from == pair || ad->to == pair);

         replaceVertex_helper(ad, pair, second);
         g.createEdge(ad->from, ad->to, ad);
      }

      for (int j = 0; j < adjacents.count(); ++j) {
         g.takeEdge(pair, adjacents.at(j));
      }

      // The pair simplified a layout vertex, so place back the correct vertex in the variable
      // that track layout vertices
      if (pair->m_item == q) {
         AnchorVertex *layoutVertex = first->m_item == q ? first : second;
         Q_ASSERT(layoutVertex->m_item == q);
         changeLayoutVertex(orientation, pair, layoutVertex);
      }

      delete pair;
   }
   qDeleteAll(parallelAnchors);
   parallelAnchors.clear();
   toRestore.clear();
}

QGraphicsAnchorLayoutPrivate::Orientation QGraphicsAnchorLayoutPrivate::edgeOrientation(Qt::AnchorPoint edge)
{
   return edge > Qt::AnchorRight ? Vertical : Horizontal;
}

void QGraphicsAnchorLayoutPrivate::createLayoutEdges()
{
   Q_Q(QGraphicsAnchorLayout);
   QGraphicsLayoutItem *layout = q;

   // Horizontal
   AnchorData *data = new AnchorData;
   addAnchor_helper(layout, Qt::AnchorLeft, layout, Qt::AnchorRight, data);
   data->maxSize = QWIDGETSIZE_MAX;

   // Save a reference to layout vertices
   layoutFirstVertex[Horizontal]   = internalVertex(layout, Qt::AnchorLeft);
   layoutCentralVertex[Horizontal] = nullptr;
   layoutLastVertex[Horizontal]    = internalVertex(layout, Qt::AnchorRight);

   // Vertical
   data = new AnchorData;
   addAnchor_helper(layout, Qt::AnchorTop, layout,
      Qt::AnchorBottom, data);
   data->maxSize = QWIDGETSIZE_MAX;

   // Save a reference to layout vertices
   layoutFirstVertex[Vertical]   = internalVertex(layout, Qt::AnchorTop);
   layoutCentralVertex[Vertical] = nullptr;
   layoutLastVertex[Vertical]    = internalVertex(layout, Qt::AnchorBottom);
}

void QGraphicsAnchorLayoutPrivate::deleteLayoutEdges()
{
   Q_Q(QGraphicsAnchorLayout);

   Q_ASSERT(!internalVertex(q, Qt::AnchorHorizontalCenter));
   Q_ASSERT(!internalVertex(q, Qt::AnchorVerticalCenter));

   removeAnchor_helper(internalVertex(q, Qt::AnchorLeft), internalVertex(q, Qt::AnchorRight));
   removeAnchor_helper(internalVertex(q, Qt::AnchorTop), internalVertex(q, Qt::AnchorBottom));
}

void QGraphicsAnchorLayoutPrivate::createItemEdges(QGraphicsLayoutItem *item)
{
   items.append(item);

   // Create horizontal and vertical CS anchors for the item and
   // refresh its size hint / policy values.
   AnchorData *data = new AnchorData;
   addAnchor_helper(item, Qt::AnchorLeft, item, Qt::AnchorRight, data);
   data->refreshSizeHints();

   data = new AnchorData;
   addAnchor_helper(item, Qt::AnchorTop, item, Qt::AnchorBottom, data);
   data->refreshSizeHints();
}

void QGraphicsAnchorLayoutPrivate::createCenterAnchors(QGraphicsLayoutItem *item, Qt::AnchorPoint centerEdge)
{
   Q_Q(QGraphicsAnchorLayout);

   Orientation orientation;
   switch (centerEdge) {
      case Qt::AnchorHorizontalCenter:
         orientation = Horizontal;
         break;
      case Qt::AnchorVerticalCenter:
         orientation = Vertical;
         break;
      default:
         // Don't create center edges unless needed
         return;
   }

   // Check if vertex already exists
   if (internalVertex(item, centerEdge)) {
      return;
   }

   // Orientation code
   Qt::AnchorPoint firstEdge;
   Qt::AnchorPoint lastEdge;

   if (orientation == Horizontal) {
      firstEdge = Qt::AnchorLeft;
      lastEdge = Qt::AnchorRight;
   } else {
      firstEdge = Qt::AnchorTop;
      lastEdge = Qt::AnchorBottom;
   }

   AnchorVertex *first = internalVertex(item, firstEdge);
   AnchorVertex *last = internalVertex(item, lastEdge);
   Q_ASSERT(first && last);

   // Create new anchors
   QSimplexConstraint *c = new QSimplexConstraint;

   AnchorData *data = new AnchorData;
   c->variables.insert(data, 1.0);
   addAnchor_helper(item, firstEdge, item, centerEdge, data);
   data->isCenterAnchor = true;
   data->dependency = AnchorData::Master;
   data->refreshSizeHints();

   data = new AnchorData;
   c->variables.insert(data, -1.0);
   addAnchor_helper(item, centerEdge, item, lastEdge, data);
   data->isCenterAnchor = true;
   data->dependency = AnchorData::Slave;
   data->refreshSizeHints();

   itemCenterConstraints[orientation].append(c);

   // Remove old one
   removeAnchor_helper(first, last);

   if (item == q) {
      layoutCentralVertex[orientation] = internalVertex(q, centerEdge);
   }
}

void QGraphicsAnchorLayoutPrivate::removeCenterAnchors(
   QGraphicsLayoutItem *item, Qt::AnchorPoint centerEdge,
   bool substitute)
{
   Q_Q(QGraphicsAnchorLayout);

   Orientation orientation;
   switch (centerEdge) {
      case Qt::AnchorHorizontalCenter:
         orientation = Horizontal;
         break;
      case Qt::AnchorVerticalCenter:
         orientation = Vertical;
         break;
      default:
         // Don't remove edges that not the center ones
         return;
   }

   // Orientation code
   Qt::AnchorPoint firstEdge;
   Qt::AnchorPoint lastEdge;

   if (orientation == Horizontal) {
      firstEdge = Qt::AnchorLeft;
      lastEdge = Qt::AnchorRight;
   } else {
      firstEdge = Qt::AnchorTop;
      lastEdge = Qt::AnchorBottom;
   }

   AnchorVertex *center = internalVertex(item, centerEdge);
   if (!center) {
      return;
   }
   AnchorVertex *first = internalVertex(item, firstEdge);

   Q_ASSERT(first);
   Q_ASSERT(center);

   Graph<AnchorVertex, AnchorData> &g = graph[orientation];


   AnchorData *oldData = g.edgeData(first, center);
   // Remove center constraint
   for (int i = itemCenterConstraints[orientation].count() - 1; i >= 0; --i) {
      if (itemCenterConstraints[orientation].at(i)->variables.contains(oldData)) {
         delete itemCenterConstraints[orientation].takeAt(i);
         break;
      }
   }

   if (substitute) {
      // Create the new anchor that should substitute the left-center-right anchors.
      AnchorData *data = new AnchorData;
      addAnchor_helper(item, firstEdge, item, lastEdge, data);
      data->refreshSizeHints();

      // Remove old anchors
      removeAnchor_helper(first, center);
      removeAnchor_helper(center, internalVertex(item, lastEdge));

   } else {
      // this is only called from removeAnchors()
      // first remove all non CS anchors

      QList<AnchorVertex *> adjacents = g.adjacentVertices(center);

      for (int i = 0; i < adjacents.count(); ++i) {
         AnchorVertex *v = adjacents.at(i);
         if (v->m_item != item) {
            removeAnchor_helper(center, internalVertex(v->m_item, v->m_edge));
         }
      }

      // when all non CS anchors are removed it will automatically merge the
      // center anchor into a left-right (or top-bottom) anchor. We must also delete this,
      // by this time, the center vertex is deleted and merged into a non-centered CS anchor
      removeAnchor_helper(first, internalVertex(item, lastEdge));
   }

   if (item == q) {
      layoutCentralVertex[orientation] = nullptr;
   }
}

void QGraphicsAnchorLayoutPrivate::removeCenterConstraints(QGraphicsLayoutItem *item,
   Orientation orientation)
{
   // Remove the item center constraints associated to this item
   // temporary solution - we should probably use a better data structure to hold items
   // and/or their associated constraints so that we can remove those easily

   AnchorVertex *first  = internalVertex(item, orientation == Horizontal ? Qt::AnchorLeft : Qt::AnchorTop);
   AnchorVertex *center = internalVertex(item, orientation == Horizontal ? Qt::AnchorHorizontalCenter : Qt::AnchorVerticalCenter);

   // skip if no center constraints exist
   if (!center) {
      return;
   }

   Q_ASSERT(first);
   AnchorData *internalAnchor = graph[orientation].edgeData(first, center);

   // look for our anchor in all item center constraints, then remove it
   for (int i = 0; i < itemCenterConstraints[orientation].size(); ++i) {
      if (itemCenterConstraints[orientation].at(i)->variables.contains(internalAnchor)) {
         delete itemCenterConstraints[orientation].takeAt(i);
         break;
      }
   }
}

QGraphicsAnchor *QGraphicsAnchorLayoutPrivate::addAnchor(QGraphicsLayoutItem *firstItem,
   Qt::AnchorPoint firstEdge, QGraphicsLayoutItem *secondItem, Qt::AnchorPoint secondEdge, qreal *spacing)
{
   Q_Q(QGraphicsAnchorLayout);
   if ((firstItem == nullptr) || (secondItem == nullptr)) {
      qWarning("QGraphicsAnchorLayout::addAnchor() Unable to anchor invalid items (nullptr)");
      return nullptr;
   }

   if (firstItem == secondItem) {
      qWarning("QGraphicsAnchorLayout::addAnchor() Unable to anchor an item to itself");
      return nullptr;
   }

   if (edgeOrientation(secondEdge) != edgeOrientation(firstEdge)) {
      qWarning("QGraphicsAnchorLayout::addAnchor() Unable to anchor edges of different orientations");
      return nullptr;
   }

   const QGraphicsLayoutItem *parentWidget = q->parentLayoutItem();
   if (firstItem == parentWidget || secondItem == parentWidget) {
      qWarning("QGraphicsAnchorLayout::addAnchor() Unable to add the parent of the layout to this layout.");
      return nullptr;
   }

   // In QGraphicsAnchorLayout, items are represented by a CS graph as four anchors which connect
   //  - Left -> HCenter
   //  - HCenter-> Right
   //  - Top -> VCenter
   //  - VCenter -> Bottom

   // ensure the CS anchors have been created for both items
   if (firstItem != q && !items.contains(firstItem)) {
      createItemEdges(firstItem);
      addChildLayoutItem(firstItem);
   }
   if (secondItem != q && !items.contains(secondItem)) {
      createItemEdges(secondItem);
      addChildLayoutItem(secondItem);
   }

   // create center edges if needed
   createCenterAnchors(firstItem, firstEdge);
   createCenterAnchors(secondItem, secondEdge);

   // use heuristics to find out what the user meant with this anchor.
   correctEdgeDirection(firstItem, firstEdge, secondItem, secondEdge);

   AnchorData *data = new AnchorData;
   QGraphicsAnchor *graphicsAnchor = acquireGraphicsAnchor(data);

   addAnchor_helper(firstItem, firstEdge, secondItem, secondEdge, data);

   if (spacing) {
      graphicsAnchor->setSpacing(*spacing);
   } else {
      // If firstItem or secondItem is the layout itself, the spacing will default to 0.
      // Otherwise, the following matrix is used (questionmark means that the spacing
      // is queried from the style):
      //                from
      //  to      Left    HCenter Right
      //  Left    0       0       ?
      //  HCenter 0       0       0
      //  Right   ?       0       0
      if (firstItem == q
         || secondItem == q
         || pickEdge(firstEdge, Horizontal) == Qt::AnchorHorizontalCenter
         || oppositeEdge(firstEdge) != secondEdge) {
         graphicsAnchor->setSpacing(0);
      } else {
         graphicsAnchor->unsetSpacing();
      }
   }

   return graphicsAnchor;
}

void QGraphicsAnchorLayoutPrivate::addAnchor_helper(QGraphicsLayoutItem *firstItem,
   Qt::AnchorPoint firstEdge, QGraphicsLayoutItem *secondItem, Qt::AnchorPoint secondEdge, AnchorData *data)
{
   Q_Q(QGraphicsAnchorLayout);

   const Orientation orientation = edgeOrientation(firstEdge);

   // Create or increase the reference count for the related vertices.
   AnchorVertex *v1 = addInternalVertex(firstItem, firstEdge);
   AnchorVertex *v2 = addInternalVertex(secondItem, secondEdge);

   // Remove previous anchor
   if (graph[orientation].edgeData(v1, v2)) {
      removeAnchor_helper(v1, v2);
   }

   // If this is a CS set the associated item
   if (firstItem == secondItem) {
      data->item = firstItem;
   }

   data->orientation = orientation;

   // Create a bi-directional edge in the sense it can be transversed both
   // from v1 or v2. "data" however is shared between the two references
   // so we still know that the anchor direction is from 1 to 2.
   data->from = v1;
   data->to   = v2;

#if defined(CS_SHOW_DEBUG_GUI_GRAPHICSVIEW)
   data->name = QString::fromLatin1("%1 --to--> %2").formatArg(v1->toString()).formatArg(v2->toString());
#endif

   // tracks CS anchors currently inside AnchorData methods
   // access to the 'q' pointer is not available
   data->isLayoutAnchor = (data->item == q);

   graph[orientation].createEdge(v1, v2, data);
}

QGraphicsAnchor *QGraphicsAnchorLayoutPrivate::getAnchor(QGraphicsLayoutItem *firstItem,
   Qt::AnchorPoint firstEdge, QGraphicsLayoutItem *secondItem, Qt::AnchorPoint secondEdge)
{
   // Do not expose CS anchors
   if (firstItem == secondItem) {
      return nullptr;
   }

   const Orientation orientation = edgeOrientation(firstEdge);
   AnchorVertex *v1 = internalVertex(firstItem, firstEdge);
   AnchorVertex *v2 = internalVertex(secondItem, secondEdge);

   QGraphicsAnchor *graphicsAnchor = nullptr;

   AnchorData *data = graph[orientation].edgeData(v1, v2);
   if (data) {
      // We could use "acquireGraphicsAnchor" here, but to avoid a regression where
      // a CS anchor was wrongly exposed, ensure no new QGraphicsAnchor instances are
      // created by this call. This assumption must hold because anchors are either
      // user-created (and already have their public object created), or they are
      // a CS anchor (and must not reach this point).

      Q_ASSERT(data->graphicsAnchor);
      graphicsAnchor = data->graphicsAnchor;
   }
   return graphicsAnchor;
}

void QGraphicsAnchorLayoutPrivate::removeAnchor(AnchorVertex *firstVertex, AnchorVertex *secondVertex)
{
   Q_Q(QGraphicsAnchorLayout);

   // Save references to items while it's safe to assume the vertices exist
   QGraphicsLayoutItem *firstItem = firstVertex->m_item;
   QGraphicsLayoutItem *secondItem = secondVertex->m_item;

   // Delete the anchor (may trigger deletion of center vertices)
   removeAnchor_helper(firstVertex, secondVertex);

   // Ensure no dangling pointer is left behind
   firstVertex  = nullptr;
   secondVertex = nullptr;

   // Checking if the item stays in the layout or not
   bool keepFirstItem = false;
   bool keepSecondItem = false;

   QPair<AnchorVertex *, int> v;
   int refcount = -1;

   if (firstItem != q) {
      for (int i = Qt::AnchorLeft; i <= Qt::AnchorBottom; ++i) {
         v = m_vertexList.value(qMakePair(firstItem, static_cast<Qt::AnchorPoint>(i)));
         if (v.first) {
            if (i == Qt::AnchorHorizontalCenter || i == Qt::AnchorVerticalCenter) {
               refcount = 2;
            } else {
               refcount = 1;
            }

            if (v.second > refcount) {
               keepFirstItem = true;
               break;
            }
         }
      }
   } else {
      keepFirstItem = true;
   }

   if (secondItem != q) {
      for (int i = Qt::AnchorLeft; i <= Qt::AnchorBottom; ++i) {
         v = m_vertexList.value(qMakePair(secondItem, static_cast<Qt::AnchorPoint>(i)));
         if (v.first) {
            if (i == Qt::AnchorHorizontalCenter || i == Qt::AnchorVerticalCenter) {
               refcount = 2;
            } else {
               refcount = 1;
            }

            if (v.second > refcount) {
               keepSecondItem = true;
               break;
            }
         }
      }
   } else {
      keepSecondItem = true;
   }

   if (!keepFirstItem) {
      q->removeAt(items.indexOf(firstItem));
   }

   if (!keepSecondItem) {
      q->removeAt(items.indexOf(secondItem));
   }

   // Removing anchors invalidates the layout
   q->invalidate();
}

void QGraphicsAnchorLayoutPrivate::removeAnchor_helper(AnchorVertex *v1, AnchorVertex *v2)
{
   Q_ASSERT(v1 && v2);

   // Remove edge from graph
   const Orientation o = edgeOrientation(v1->m_edge);
   graph[o].removeEdge(v1, v2);

   // Decrease vertices reference count (may trigger a deletion)
   removeInternalVertex(v1->m_item, v1->m_edge);
   removeInternalVertex(v2->m_item, v2->m_edge);
}

AnchorVertex *QGraphicsAnchorLayoutPrivate::addInternalVertex(QGraphicsLayoutItem *item, Qt::AnchorPoint edge)
{
   QPair<QGraphicsLayoutItem *, Qt::AnchorPoint> pair(item, edge);
   QPair<AnchorVertex *, int> v = m_vertexList.value(pair);

   if (!v.first) {
      Q_ASSERT(v.second == 0);
      v.first = new AnchorVertex(item, edge);
   }
   v.second++;
   m_vertexList.insert(pair, v);
   return v.first;
}

void QGraphicsAnchorLayoutPrivate::removeInternalVertex(QGraphicsLayoutItem *item, Qt::AnchorPoint edge)
{
   QPair<QGraphicsLayoutItem *, Qt::AnchorPoint> pair(item, edge);
   QPair<AnchorVertex *, int> v = m_vertexList.value(pair);

   if (!v.first) {
      qWarning("QGraphicsAnchorLayout::removeInternalVertex() This edge is not in the graph");
      return;
   }

   v.second--;
   if (v.second == 0) {
      // Remove reference and delete vertex
      m_vertexList.remove(pair);
      delete v.first;
   } else {
      // Update reference count
      m_vertexList.insert(pair, v);

      if ((v.second == 2) &&
         ((edge == Qt::AnchorHorizontalCenter) ||
            (edge == Qt::AnchorVerticalCenter))) {
         removeCenterAnchors(item, edge, true);
      }
   }
}

void QGraphicsAnchorLayoutPrivate::removeVertex(QGraphicsLayoutItem *item, Qt::AnchorPoint edge)
{
   if (AnchorVertex *v = internalVertex(item, edge)) {
      Graph<AnchorVertex, AnchorData> &g = graph[edgeOrientation(edge)];
      const QList<AnchorVertex *> allVertices = graph[edgeOrientation(edge)].adjacentVertices(v);

      for (AnchorVertex *v2 : allVertices) {
         g.removeEdge(v, v2);
         removeInternalVertex(item, edge);
         removeInternalVertex(v2->m_item, v2->m_edge);
      }
   }
}

void QGraphicsAnchorLayoutPrivate::removeAnchors(QGraphicsLayoutItem *item)
{
   // remove the center anchor first!!
   removeCenterAnchors(item, Qt::AnchorHorizontalCenter, false);
   removeVertex(item, Qt::AnchorLeft);
   removeVertex(item, Qt::AnchorRight);

   removeCenterAnchors(item, Qt::AnchorVerticalCenter, false);
   removeVertex(item, Qt::AnchorTop);
   removeVertex(item, Qt::AnchorBottom);
}

void QGraphicsAnchorLayoutPrivate::correctEdgeDirection(QGraphicsLayoutItem *&firstItem,
      Qt::AnchorPoint &firstEdge, QGraphicsLayoutItem *&secondItem, Qt::AnchorPoint &secondEdge)
{
   Q_Q(QGraphicsAnchorLayout);

   if ((firstItem != q) && (secondItem != q)) {
      // If connection is between widgets (not the layout itself)
      // Ensure that "right-edges" sit to the left of "left-edges".
      if (firstEdge < secondEdge) {
         qSwap(firstItem, secondItem);
         qSwap(firstEdge, secondEdge);
      }
   } else if (firstItem == q) {
      // If connection involves the right or bottom of a layout, ensure
      // the layout is the second item.
      if ((firstEdge == Qt::AnchorRight) || (firstEdge == Qt::AnchorBottom)) {
         qSwap(firstItem, secondItem);
         qSwap(firstEdge, secondEdge);
      }
   } else if ((secondEdge != Qt::AnchorRight) && (secondEdge != Qt::AnchorBottom)) {
      // If connection involves the left, center or top of layout, ensure
      // the layout is the first item.
      qSwap(firstItem, secondItem);
      qSwap(firstEdge, secondEdge);
   }
}

QLayoutStyleInfo &QGraphicsAnchorLayoutPrivate::styleInfo() const
{
   if (styleInfoDirty) {
      Q_Q(const QGraphicsAnchorLayout);

      //### Fix this if QGV ever gets support for Metal style or different Aqua sizes.
      QWidget *wid = nullptr;

      QGraphicsLayoutItem *parent = q->parentLayoutItem();
      while (parent && parent->isLayout()) {
         parent = parent->parentLayoutItem();
      }

      QGraphicsWidget *w = nullptr;
      if (parent) {
         QGraphicsItem *parentItem = parent->graphicsItem();
         if (parentItem && parentItem->isWidget()) {
            w = static_cast<QGraphicsWidget *>(parentItem);
         }
      }

      QStyle *style = w ? w->style() : QApplication::style();
      cachedStyleInfo = QLayoutStyleInfo(style, wid);
      cachedStyleInfo.setDefaultSpacing(Qt::Horizontal, spacings[0]);
      cachedStyleInfo.setDefaultSpacing(Qt::Vertical, spacings[1]);

      styleInfoDirty = false;
   }
   return cachedStyleInfo;
}

void QGraphicsAnchorLayoutPrivate::calculateGraphs()
{
   if (!calculateGraphCacheDirty) {
      return;
   }
   calculateGraphs(Horizontal);
   calculateGraphs(Vertical);
   calculateGraphCacheDirty = false;
}

// Maybe getGraphParts could return the variables when traversing
QList<AnchorData *> getVariables(const QList<QSimplexConstraint *> &constraints)
{
   QSet<AnchorData *> variableSet;
   for (int i = 0; i < constraints.count(); ++i) {
      const QSimplexConstraint *c = constraints.at(i);

      for (QSimplexVariable *var : c->variables.keys()) {
         variableSet += static_cast<AnchorData *>(var);
      }
   }
   return variableSet.toList();
}

void QGraphicsAnchorLayoutPrivate::calculateGraphs(QGraphicsAnchorLayoutPrivate::Orientation orientation)
{
   static bool simplificationEnabled = qgetenv("QT_ANCHORLAYOUT_NO_SIMPLIFICATION").isEmpty();

   // Reset the nominal sizes of each anchor based on the current item sizes
   refreshAllSizeHints(orientation);

   // Simplify the graph
   if (simplificationEnabled && !simplifyGraph(orientation)) {
      qWarning("QGraphicsAnchorLayout::calculateGraphs() Anchor setup is not valid");
      graphHasConflicts[orientation] = true;
      return;
   }

   // Traverse all graph edges and store the possible paths to each vertex
   findPaths(orientation);

   // From the paths calculated above, extract the constraints that the current
   // anchor setup impose, to our Linear Programming problem.
   constraintsFromPaths(orientation);

   // Split the constraints and anchors into groups that should be fed to the
   // simplex solver independently. Currently we find two groups:
   //
   //  1) The "trunk", that is, the set of anchors (items) that are connected
   //     to the two opposite sides of our layout, and thus need to stretch in
   //     order to fit in the current layout size.
   //
   //  2) The floating or semi-floating anchors (items) that are those which
   //     are connected to only one (or none) of the layout sides, thus are not
   //     influenced by the layout size.
   QList<QList<QSimplexConstraint *>> parts = getGraphParts(orientation);

   // Now run the simplex solver to calculate Minimum, Preferred and Maximum sizes
   // of the "trunk" set of constraints and variables.
   // ### does trunk always exist? empty = trunk is the layout left->center->right
   QList<QSimplexConstraint *> trunkConstraints = parts.at(0);
   QList<AnchorData *> trunkVariables = getVariables(trunkConstraints);

   // For minimum and maximum, use the path between the two layout sides as the
   // objective function.
   AnchorVertex *v = layoutLastVertex[orientation];
   GraphPath trunkPath = graphPaths[orientation].value(v);

   bool feasible = calculateTrunk(orientation, trunkPath, trunkConstraints, trunkVariables);

   // For the other parts that not the trunk, solve only for the preferred size
   // that is the size they will remain at, since they are not stretched by the
   // layout.

   // Skipping the first (trunk)
   for (int i = 1; i < parts.count(); ++i) {
      if (!feasible) {
         break;
      }

      QList<QSimplexConstraint *> partConstraints = parts.at(i);
      QList<AnchorData *> partVariables = getVariables(partConstraints);
      Q_ASSERT(!partVariables.isEmpty());
      feasible &= calculateNonTrunk(partConstraints, partVariables);
   }

   // Propagate the new sizes down the simplified graph, ie. tell the
   // group anchors to set their children anchors sizes.
   updateAnchorSizes(orientation);

   graphHasConflicts[orientation] = !feasible;

   // Clean up our data structures. They are not needed anymore since
   // distribution uses just interpolation.
   qDeleteAll(m_constraints[orientation]);
   m_constraints[orientation].clear();
   graphPaths[orientation].clear();

   if (simplificationEnabled) {
      restoreSimplifiedGraph(orientation);
   }
}

static void shiftConstraints(const QList<QSimplexConstraint *> &constraints, qreal amount)
{
   for (int i = 0; i < constraints.count(); ++i) {
      QSimplexConstraint *c = constraints.at(i);
      qreal multiplier = 0;

      for (qreal v : c->variables) {
         multiplier += v;
      }
      c->constant += multiplier * amount;
   }
}

bool QGraphicsAnchorLayoutPrivate::calculateTrunk(Orientation orientation, const GraphPath &path,
      const QList<QSimplexConstraint *> &constraints, const QList<AnchorData *> &variables)
{
   bool feasible = true;
   bool needsSimplex = !constraints.isEmpty();

   if (needsSimplex) {

      QList<QSimplexConstraint *> sizeHintConstraints = constraintsFromSizeHints(variables);
      QList<QSimplexConstraint *> allConstraints = constraints + sizeHintConstraints;

      shiftConstraints(allConstraints, g_offset);

      // Solve min and max size hints
      qreal min, max;
      feasible = solveMinMax(allConstraints, path, &min, &max);

      if (feasible) {
         solvePreferred(constraints, variables);

         // Calculate and set the preferred size for the layout,
         // from the edge sizes that were calculated above.
         qreal pref(0.0);

         for (const AnchorData *ad : path.positives) {
            pref += ad->sizeAtPreferred;
         }

         for (const AnchorData *ad : path.negatives) {
            pref -= ad->sizeAtPreferred;
         }

         sizeHints[orientation][Qt::MinimumSize] = min;
         sizeHints[orientation][Qt::PreferredSize] = pref;
         sizeHints[orientation][Qt::MaximumSize] = max;
      }

      qDeleteAll(sizeHintConstraints);
      shiftConstraints(constraints, -g_offset);

   } else {
      // No Simplex is necessary because the path was simplified all the way to a single
      // anchor.
      Q_ASSERT(path.positives.count() == 1);
      Q_ASSERT(path.negatives.count() == 0);

      AnchorData *ad = path.positives.toList()[0];
      ad->sizeAtMinimum = ad->minSize;
      ad->sizeAtPreferred = ad->prefSize;
      ad->sizeAtMaximum = ad->maxSize;

      sizeHints[orientation][Qt::MinimumSize] = ad->sizeAtMinimum;
      sizeHints[orientation][Qt::PreferredSize] = ad->sizeAtPreferred;
      sizeHints[orientation][Qt::MaximumSize] = ad->sizeAtMaximum;
   }

#if defined(CS_SHOW_DEBUG_GUI_GRAPHICSVIEW)
   lastCalculationUsedSimplex[orientation] = needsSimplex;
#endif

   return feasible;
}

bool QGraphicsAnchorLayoutPrivate::calculateNonTrunk(const QList<QSimplexConstraint *> &constraints,
   const QList<AnchorData *> &variables)
{
   shiftConstraints(constraints, g_offset);
   bool feasible = solvePreferred(constraints, variables);

   if (feasible) {
      // Propagate size at preferred to other sizes. Semi-floats always will be
      // in their sizeAtPreferred.
      for (int j = 0; j < variables.count(); ++j) {
         AnchorData *ad = variables.at(j);
         Q_ASSERT(ad);
         ad->sizeAtMinimum = ad->sizeAtPreferred;
         ad->sizeAtMaximum = ad->sizeAtPreferred;
      }
   }

   shiftConstraints(constraints, -g_offset);
   return feasible;
}

void QGraphicsAnchorLayoutPrivate::refreshAllSizeHints(Orientation orientation)
{
   Graph<AnchorVertex, AnchorData> &g = graph[orientation];
   QList<QPair<AnchorVertex *, AnchorVertex *>> vertices = g.connections();

   QLayoutStyleInfo styleInf = styleInfo();
   for (int i = 0; i < vertices.count(); ++i) {
      AnchorData *data = g.edgeData(vertices.at(i).first, vertices.at(i).second);
      data->refreshSizeHints(&styleInf);
   }
}

void QGraphicsAnchorLayoutPrivate::findPaths(Orientation orientation)
{
   QQueue<QPair<AnchorVertex *, AnchorVertex *>> queue;

   QSet<AnchorData *> visited;

   AnchorVertex *root = layoutFirstVertex[orientation];

   graphPaths[orientation].insert(root, GraphPath());

   for (AnchorVertex *v : graph[orientation].adjacentVertices(root)) {
      queue.enqueue(qMakePair(root, v));
   }

   while (!queue.isEmpty()) {
      QPair<AnchorVertex *, AnchorVertex *>  pair = queue.dequeue();
      AnchorData *edge = graph[orientation].edgeData(pair.first, pair.second);

      if (visited.contains(edge)) {
         continue;
      }

      visited.insert(edge);
      GraphPath current = graphPaths[orientation].value(pair.first);

      if (edge->from == pair.first) {
         current.positives.insert(edge);
      } else {
         current.negatives.insert(edge);
      }

      graphPaths[orientation].insert(pair.second, current);

      for (AnchorVertex *v : graph[orientation].adjacentVertices(pair.second)) {
         queue.enqueue(qMakePair(pair.second, v));
      }
   }

   // We will walk through every reachable items (non-float) store them in a temporary set.
   // We them create a set of all items and subtract the non-floating items from the set in
   // order to get the floating items. The floating items is then stored in m_floatItems
   identifyFloatItems(visited, orientation);
}

void QGraphicsAnchorLayoutPrivate::constraintsFromPaths(Orientation orientation)
{
   for (AnchorVertex *vertex : graphPaths[orientation].uniqueKeys()) {
      int valueCount = graphPaths[orientation].count(vertex);

      if (valueCount == 1) {
         continue;
      }

      QList<GraphPath> pathsToVertex = graphPaths[orientation].values(vertex);

      for (int i = 1; i < valueCount; ++i) {
         m_constraints[orientation] += pathsToVertex[0].constraint(pathsToVertex.at(i));
      }
   }
}

void QGraphicsAnchorLayoutPrivate::updateAnchorSizes(Orientation orientation)
{
   Graph<AnchorVertex, AnchorData> &g = graph[orientation];
   const QList<QPair<AnchorVertex *, AnchorVertex *>> &vertices = g.connections();

   for (int i = 0; i < vertices.count(); ++i) {
      AnchorData *ad = g.edgeData(vertices.at(i).first, vertices.at(i).second);
      ad->updateChildrenSizes();
   }
}

QList<QSimplexConstraint *> QGraphicsAnchorLayoutPrivate::constraintsFromSizeHints(const QList<AnchorData *> &anchors)
{
   if (anchors.isEmpty()) {
      return QList<QSimplexConstraint *>();
   }

   // Look for the layout edge. That can be either the first half in case the
   // layout is split in two, or the whole layout anchor.
   Orientation orient = Orientation(anchors.first()->orientation);
   AnchorData *layoutEdge = nullptr;

   if (layoutCentralVertex[orient]) {
      layoutEdge = graph[orient].edgeData(layoutFirstVertex[orient], layoutCentralVertex[orient]);
   } else {
      layoutEdge = graph[orient].edgeData(layoutFirstVertex[orient], layoutLastVertex[orient]);
   }

   // If maxSize is less then "infinite", that means there are other anchors
   // grouped together with this one. We can't ignore its maximum value so we
   // set back the variable to NULL to prevent the continue condition from being
   // satisfied in the loop below.

   const qreal expectedMax = layoutCentralVertex[orient] ? QWIDGETSIZE_MAX / 2 : QWIDGETSIZE_MAX;
   qreal actualMax;

   if (layoutEdge->from == layoutFirstVertex[orient]) {
      actualMax = layoutEdge->maxSize;
   } else {
      actualMax = -layoutEdge->minSize;
   }
   if (actualMax != expectedMax) {
      layoutEdge = nullptr;
   }

   // For each variable, create constraints based on size hints
   QList<QSimplexConstraint *> anchorConstraints;
   bool unboundedProblem = true;
   for (int i = 0; i < anchors.size(); ++i) {
      AnchorData *ad = anchors.at(i);

      // Anchors that have their size directly linked to another one don't need constraints
      // For exammple, the second half of an item has exactly the same size as the first half
      // thus constraining the latter is enough.
      if (ad->dependency == AnchorData::Slave) {
         continue;
      }

      // To use negative variables inside simplex, we shift them so the minimum negative value is
      // mapped to zero before solving. To make sure that it works, we need to guarantee that the
      // variables are all inside a certain boundary.
      qreal boundedMin = qBound(-g_offset, ad->minSize, g_offset);
      qreal boundedMax = qBound(-g_offset, ad->maxSize, g_offset);

      if ((boundedMin == boundedMax) || qFuzzyCompare(boundedMin, boundedMax)) {
         QSimplexConstraint *c = new QSimplexConstraint;
         c->variables.insert(ad, 1.0);
         c->constant = boundedMin;
         c->ratio = QSimplexConstraint::Equal;
         anchorConstraints += c;
         unboundedProblem = false;

      } else {
         QSimplexConstraint *c = new QSimplexConstraint;
         c->variables.insert(ad, 1.0);
         c->constant = boundedMin;
         c->ratio = QSimplexConstraint::MoreOrEqual;
         anchorConstraints += c;

         // avoid adding restrictions to the layout CS anchors
         if (ad == layoutEdge) {
            continue;
         }

         c = new QSimplexConstraint;
         c->variables.insert(ad, 1.0);
         c->constant = boundedMax;
         c->ratio = QSimplexConstraint::LessOrEqual;
         anchorConstraints += c;
         unboundedProblem = false;
      }
   }

   // If no upper boundary restriction was added, add one to avoid unbounded problem
   if (unboundedProblem) {
      QSimplexConstraint *c = new QSimplexConstraint;
      c->variables.insert(layoutEdge, 1.0);
      // The maximum size that the layout can take
      c->constant = g_offset;
      c->ratio = QSimplexConstraint::LessOrEqual;
      anchorConstraints += c;
   }

   return anchorConstraints;
}

QList< QList<QSimplexConstraint *>> QGraphicsAnchorLayoutPrivate::getGraphParts(Orientation orientation)
{
   Q_ASSERT(layoutFirstVertex[orientation] && layoutLastVertex[orientation]);

   AnchorData *edgeL1 = nullptr;
   AnchorData *edgeL2 = nullptr;

   // The layout may have a single anchor between Left and Right or two half anchors
   // passing through the center
   if (layoutCentralVertex[orientation]) {
      edgeL1 = graph[orientation].edgeData(layoutFirstVertex[orientation], layoutCentralVertex[orientation]);
      edgeL2 = graph[orientation].edgeData(layoutCentralVertex[orientation], layoutLastVertex[orientation]);
   } else {
      edgeL1 = graph[orientation].edgeData(layoutFirstVertex[orientation], layoutLastVertex[orientation]);
   }

   QLinkedList<QSimplexConstraint *> remainingConstraints;

   for (int i = 0; i < m_constraints[orientation].count(); ++i) {
      remainingConstraints += m_constraints[orientation].at(i);
   }

   for (int i = 0; i < itemCenterConstraints[orientation].count(); ++i) {
      remainingConstraints += itemCenterConstraints[orientation].at(i);
   }

   QList<QSimplexConstraint *> trunkConstraints;
   QSet<QSimplexVariable *> trunkVariables;

   trunkVariables += edgeL1;
   if (edgeL2) {
      trunkVariables += edgeL2;
   }

   bool dirty;
   do {
      dirty = false;

      QLinkedList<QSimplexConstraint *>::iterator it = remainingConstraints.begin();
      while (it != remainingConstraints.end()) {
         QSimplexConstraint *c = *it;
         bool match = false;

         // Check if this constraint have some overlap with current trunk variables
         for (QSimplexVariable *ad : trunkVariables) {
            if (c->variables.contains(ad)) {
               match = true;
               break;
            }
         }

         // If so, we add it to trunk, and erase it from the
         // remaining constraints.
         if (match) {
            trunkConstraints += c;
            trunkVariables += QSet<QSimplexVariable *>::fromList(c->variables.keys());
            it = remainingConstraints.erase(it);
            dirty = true;
         } else {
            // Note that we don't erase the constraint if it's not
            // a match, since in a next iteration of a do-while we
            // can pass on it again and it will be a match.
            //
            // For example: if trunk share a variable with
            // remainingConstraints[1] and it shares with
            // remainingConstraints[0], we need a second iteration
            // of the do-while loop to match both.
            ++it;
         }
      }
   } while (dirty);

   QList< QList<QSimplexConstraint *>> result;
   result += trunkConstraints;

   if (!remainingConstraints.isEmpty()) {
      QList<QSimplexConstraint *> nonTrunkConstraints;
      QLinkedList<QSimplexConstraint *>::iterator it = remainingConstraints.begin();
      while (it != remainingConstraints.end()) {
         nonTrunkConstraints += *it;
         ++it;
      }
      result += nonTrunkConstraints;
   }

   return result;
}

void QGraphicsAnchorLayoutPrivate::identifyFloatItems(const QSet<AnchorData *> &visited, Orientation orientation)
{
   QSet<QGraphicsLayoutItem *> nonFloating;

   for (const AnchorData *ad : visited) {
      identifyNonFloatItems_helper(ad, &nonFloating);
   }

   QSet<QGraphicsLayoutItem *> allItems;

   for (QGraphicsLayoutItem *item : items) {
      allItems.insert(item);
   }

   m_floatItems[orientation] = allItems - nonFloating;
}

void QGraphicsAnchorLayoutPrivate::identifyNonFloatItems_helper(const AnchorData *ad,
      QSet<QGraphicsLayoutItem *> *nonFloatingItemsIdentifiedSoFar)
{
   Q_Q(QGraphicsAnchorLayout);

   switch (ad->type) {
      case AnchorData::Normal:
         if (ad->item && ad->item != q) {
            nonFloatingItemsIdentifiedSoFar->insert(ad->item);
         }
         break;

      case AnchorData::Sequential:
         for (const AnchorData *d : static_cast<const SequentialAnchorData *>(ad)->m_edges) {
            identifyNonFloatItems_helper(d, nonFloatingItemsIdentifiedSoFar);
         }

         break;
      case AnchorData::Parallel:
         identifyNonFloatItems_helper(static_cast<const ParallelAnchorData *>(ad)->firstEdge, nonFloatingItemsIdentifiedSoFar);
         identifyNonFloatItems_helper(static_cast<const ParallelAnchorData *>(ad)->secondEdge, nonFloatingItemsIdentifiedSoFar);
         break;
   }
}

void QGraphicsAnchorLayoutPrivate::setItemsGeometries(const QRectF &geom)
{
   Q_Q(QGraphicsAnchorLayout);
   AnchorVertex *firstH, *secondH, *firstV, *secondV;

   qreal top;
   qreal left;
   qreal right;

   q->getContentsMargins(&left, &top, &right, nullptr);
   const Qt::LayoutDirection visualDir = visualDirection();

   if (visualDir == Qt::RightToLeft) {
      qSwap(left, right);
   }

   left += geom.left();
   top  += geom.top();
   right = geom.right() - right;

   for (QGraphicsLayoutItem *item : items) {
      QRectF newGeom;
      QSizeF itemPreferredSize = item->effectiveSizeHint(Qt::PreferredSize);

      if (m_floatItems[Horizontal].contains(item)) {
         newGeom.setLeft(0);
         newGeom.setRight(itemPreferredSize.width());
      } else {
         firstH = internalVertex(item, Qt::AnchorLeft);
         secondH = internalVertex(item, Qt::AnchorRight);

         if (visualDir == Qt::LeftToRight) {
            newGeom.setLeft(left + firstH->distance);
            newGeom.setRight(left + secondH->distance);
         } else {
            newGeom.setLeft(right - secondH->distance);
            newGeom.setRight(right - firstH->distance);
         }
      }

      if (m_floatItems[Vertical].contains(item)) {
         newGeom.setTop(0);
         newGeom.setBottom(itemPreferredSize.height());
      } else {
         firstV = internalVertex(item, Qt::AnchorTop);
         secondV = internalVertex(item, Qt::AnchorBottom);

         newGeom.setTop(top + firstV->distance);
         newGeom.setBottom(top + secondV->distance);
      }

      item->setGeometry(newGeom);
   }
}

void QGraphicsAnchorLayoutPrivate::calculateVertexPositions(QGraphicsAnchorLayoutPrivate::Orientation orientation)
{
   QQueue<QPair<AnchorVertex *, AnchorVertex *>> queue;
   QSet<AnchorVertex *> visited;

   // Get root vertex
   AnchorVertex *root = layoutFirstVertex[orientation];

   root->distance = 0;
   visited.insert(root);

   // Add initial edges to the queue
   for (AnchorVertex *v : graph[orientation].adjacentVertices(root)) {
      queue.enqueue(qMakePair(root, v));
   }

   // Do initial calculation required by "interpolateEdge()"
   setupEdgesInterpolation(orientation);

   // Traverse the graph and calculate vertex positions
   while (!queue.isEmpty()) {
      QPair<AnchorVertex *, AnchorVertex *> pair = queue.dequeue();
      AnchorData *edge = graph[orientation].edgeData(pair.first, pair.second);

      if (visited.contains(pair.second)) {
         continue;
      }

      visited.insert(pair.second);
      interpolateEdge(pair.first, edge);

      QList<AnchorVertex *> adjacents = graph[orientation].adjacentVertices(pair.second);
      for (int i = 0; i < adjacents.count(); ++i) {
         if (!visited.contains(adjacents.at(i))) {
            queue.enqueue(qMakePair(pair.second, adjacents.at(i)));
         }
      }
   }
}

void QGraphicsAnchorLayoutPrivate::setupEdgesInterpolation(Orientation orientation)
{
   Q_Q(QGraphicsAnchorLayout);

   qreal current;
   current = (orientation == Horizontal) ? q->contentsRect().width() : q->contentsRect().height();

   QPair<Interval, qreal> result;
   result = getFactor(current,
         sizeHints[orientation][Qt::MinimumSize],
         sizeHints[orientation][Qt::PreferredSize],
         sizeHints[orientation][Qt::PreferredSize],
         sizeHints[orientation][Qt::PreferredSize],
         sizeHints[orientation][Qt::MaximumSize]);

   interpolationInterval[orientation] = result.first;
   interpolationProgress[orientation] = result.second;
}

void QGraphicsAnchorLayoutPrivate::interpolateEdge(AnchorVertex *base, AnchorData *edge)
{
   const Orientation orientation = Orientation(edge->orientation);
   const QPair<Interval, qreal> factor(interpolationInterval[orientation],
      interpolationProgress[orientation]);

   qreal edgeDistance = interpolate(factor, edge->sizeAtMinimum, edge->sizeAtPreferred,
         edge->sizeAtPreferred, edge->sizeAtPreferred,
         edge->sizeAtMaximum);

   Q_ASSERT(edge->from == base || edge->to == base);

   // Calculate the distance for the vertex opposite to the base
   if (edge->from == base) {
      edge->to->distance = base->distance + edgeDistance;
   } else {
      edge->from->distance = base->distance - edgeDistance;
   }
}

bool QGraphicsAnchorLayoutPrivate::solveMinMax(const QList<QSimplexConstraint *> &constraints,
   GraphPath path, qreal *min, qreal *max)
{
   QSimplex simplex;
   bool feasible = simplex.setConstraints(constraints);
   if (feasible) {
      // Obtain the objective constraint
      QSimplexConstraint objective;
      QSet<AnchorData *>::const_iterator iter;
      for (iter = path.positives.constBegin(); iter != path.positives.constEnd(); ++iter) {
         objective.variables.insert(*iter, 1.0);
      }

      for (iter = path.negatives.constBegin(); iter != path.negatives.constEnd(); ++iter) {
         objective.variables.insert(*iter, -1.0);
      }

      const qreal objectiveOffset = (path.positives.count() - path.negatives.count()) * g_offset;
      simplex.setObjective(&objective);

      // Calculate minimum values
      *min = simplex.solveMin() - objectiveOffset;

      // Save sizeAtMinimum results
      QList<AnchorData *> variables = getVariables(constraints);
      for (int i = 0; i < variables.size(); ++i) {
         AnchorData *ad = static_cast<AnchorData *>(variables.at(i));
         ad->sizeAtMinimum = ad->result - g_offset;
      }

      // Calculate maximum values
      *max = simplex.solveMax() - objectiveOffset;

      // Save sizeAtMaximum results
      for (int i = 0; i < variables.size(); ++i) {
         AnchorData *ad = static_cast<AnchorData *>(variables.at(i));
         ad->sizeAtMaximum = ad->result - g_offset;
      }
   }

   return feasible;
}

enum slackType {
   Grower   = -1,
   Shrinker = 1
};

static QPair<QSimplexVariable *, QSimplexConstraint *> createSlack(QSimplexConstraint *sizeConstraint,
   qreal interval, slackType type)
{
   QSimplexVariable *slack = new QSimplexVariable;
   sizeConstraint->variables.insert(slack, type);

   QSimplexConstraint *limit = new QSimplexConstraint;
   limit->variables.insert(slack, 1.0);
   limit->ratio = QSimplexConstraint::LessOrEqual;
   limit->constant = interval;

   return qMakePair(slack, limit);
}

bool QGraphicsAnchorLayoutPrivate::solvePreferred(const QList<QSimplexConstraint *> &constraints,
   const QList<AnchorData *> &variables)
{
   QList<QSimplexConstraint *> preferredConstraints;
   QList<QSimplexVariable *> preferredVariables;
   QSimplexConstraint objective;

   // Fill the objective coefficients for this variable. In the
   // end the objective function will be
   //
   //     z = n * (A_shrinker_hard + A_grower_hard + B_shrinker_hard + B_grower_hard + ...) +
   //             (A_shrinker_soft + A_grower_soft + B_shrinker_soft + B_grower_soft + ...)
   //
   // where n is the number of variables that have
   // slacks. Note that here we use the number of variables
   // as coefficient, this is to mark the "shrinker slack
   // variable" less likely to get value than the "grower
   // slack variable".

   // This will fill the values for the structural constraints
   // and we now fill the values for the slack constraints (one per variable),
   // which have this form (the constant A_pref was set when creating the slacks):
   //
   //      A + A_shrinker_hard + A_shrinker_soft - A_grower_hard - A_grower_soft = A_pref
   //
   for (int i = 0; i < variables.size(); ++i) {
      AnchorData *ad = variables.at(i);

      // The layout original structure anchors are not relevant in preferred size calculation
      if (ad->isLayoutAnchor) {
         continue;
      }

      // By default, all variables are equal to their preferred size. If they have room to
      // grow or shrink, such flexibility will be added by the additional variables below.
      QSimplexConstraint *sizeConstraint = new QSimplexConstraint;
      preferredConstraints += sizeConstraint;
      sizeConstraint->variables.insert(ad, 1.0);
      sizeConstraint->constant = ad->prefSize + g_offset;

      // Can easily shrink
      QPair<QSimplexVariable *, QSimplexConstraint *> slack;
      const qreal softShrinkInterval = ad->prefSize - ad->minPrefSize;
      if (softShrinkInterval) {
         slack = createSlack(sizeConstraint, softShrinkInterval, Shrinker);
         preferredVariables += slack.first;
         preferredConstraints += slack.second;

         // Add to objective with ratio == 1 (soft)
         objective.variables.insert(slack.first, 1.0);
      }

      // Can easily grow
      const qreal softGrowInterval = ad->maxPrefSize - ad->prefSize;
      if (softGrowInterval) {
         slack = createSlack(sizeConstraint, softGrowInterval, Grower);
         preferredVariables += slack.first;
         preferredConstraints += slack.second;

         // Add to objective with ratio == 1 (soft)
         objective.variables.insert(slack.first, 1.0);
      }

      // Can shrink if really necessary
      const qreal hardShrinkInterval = ad->minPrefSize - ad->minSize;
      if (hardShrinkInterval) {
         slack = createSlack(sizeConstraint, hardShrinkInterval, Shrinker);
         preferredVariables += slack.first;
         preferredConstraints += slack.second;

         // Add to objective with ratio == N (hard)
         objective.variables.insert(slack.first, variables.size());
      }

      // Can grow if really necessary
      const qreal hardGrowInterval = ad->maxSize - ad->maxPrefSize;
      if (hardGrowInterval) {
         slack = createSlack(sizeConstraint, hardGrowInterval, Grower);
         preferredVariables += slack.first;
         preferredConstraints += slack.second;

         // Add to objective with ratio == N (hard)
         objective.variables.insert(slack.first, variables.size());
      }
   }

   QSimplex *simplex = new QSimplex;
   bool feasible = simplex->setConstraints(constraints + preferredConstraints);
   if (feasible) {
      simplex->setObjective(&objective);

      // Calculate minimum values
      simplex->solveMin();

      // Save sizeAtPreferred results
      for (int i = 0; i < variables.size(); ++i) {
         AnchorData *ad = variables.at(i);
         ad->sizeAtPreferred = ad->result - g_offset;
      }
   }

   // Make sure we delete the simplex solver -before- we delete the
   // constraints used by it.
   delete simplex;

   // Delete constraints and variables we created.
   qDeleteAll(preferredConstraints);
   qDeleteAll(preferredVariables);

   return feasible;
}

bool QGraphicsAnchorLayoutPrivate::hasConflicts() const
{
   QGraphicsAnchorLayoutPrivate *that = const_cast<QGraphicsAnchorLayoutPrivate *>(this);
   that->calculateGraphs();

   bool floatConflict = !m_floatItems[0].isEmpty() || !m_floatItems[1].isEmpty();

   return graphHasConflicts[0] || graphHasConflicts[1] || floatConflict;
}

#if defined(CS_SHOW_DEBUG_GUI_GRAPHICSVIEW)
void QGraphicsAnchorLayoutPrivate::dumpGraph(const QString &name)
{
   QFile file(QString("anchorlayout.%1.dot").formatArg(name));

   if (! file.open(QIODevice::WriteOnly | QIODevice::Text | QIODevice::Truncate)) {
      qWarning("QGraphicsAnchorLayout::dumpGraph() Unable to write to %s", csPrintable(file.fileName()));
   }

   QString str = "digraph anchorlayout {\nnode [shape=\"rect\"]\n%1}";
   QString dotContents = graph[0].serializeToDot();
   dotContents += graph[1].serializeToDot();

   file.write(str.formatArg(dotContents).toUtf8());
   file.close();
}
#endif

#endif //QT_NO_GRAPHICSVIEW
